Problem statement: zenit11ckf

f) (25 bodov)

V tejto úlohe budeš pomáhať vyhodnocovať testy zo streľby laserových zbraní. Úžasné technológie z celého vesmíru prúdia už aj na našu planétu a organizácia, ktorá ťa zamestnáva, chce zaviesť testy na zbrojné preukazy pre tieto technológie. Na skúške má adept pred sebou pohybujúce sa premietané trojuholníky na plátne a jeho úlohou je čo najviac týchto trojuholníkov trafiť. Pomôžte oddeleniu dokladov a licencií a napíšte program, ktorý bude pomáhať tieto skúšky vyhodnocovať. Vstupom programu bude stav plachty v momente výstrelu. Vypíšte utriedený zoznam objektov, ktoré boli zasiahnuté.

Prvý riadok vstupu obsahuje tri čísla: X Y K, kde X,Y sú súradnice zásahu a K je počet trojuholníkov (1 <= K <= 50). Nasleduje K riadkov, na každom sú súradnice troch bodov tvoriacich trojuholník, ktorý vznikol projekciou objektu v čase výstrelu. Súradnice všetkých bodov na vstupe sú celé čísla a v absolútnej hodnote nepresahujú 10,000. Môžete predpokladať, že body tvoriace jeden trojuholník neležia na priamke. Na jediný riadok výstupu vypíšte medzerami oddelený zoznam čísel objektov, ktoré boli zasiahnuté. Ak sa miesto výstrelu nachádza na okraji trojuholníka, počíta sa to za zásah. Zoznam musí byť utriedený vzostupne. Ak nebol zasiahnutý žiadny objekt, nechajte výstup prázdny.

Príklad:

Vstup:

0 0 3
-1 -1 1 -1 0 2
5 5 6 6 5 6
-1 -1 1 1 -1 1

Výstup:

1 3

Vstup:

1 1 2
-10000 10000 10000 -10000 10000 10000
-9000 10000 10000 -9000 10000 10000

Výstup:

1